Product Code Database
The even–odd rule is an algorithm implemented in vector-based graphic software,J. D. Foley, A. van Dam, S. K. Feiner, and J. F. Hughes. Computer Graphics: Principles and Practice. The Systems Programming Series. Addison-Wesley, Reading, 2nd edition, 1990. like the PostScript language and Scalable Vector Graphics (SVG), which determines how a graphical shape with more than one closed outline will be filled. Unlike the nonzero-rule algorithm, this algorithm will alternatively color and leave uncolored shapes defined by nested closed paths irrespective of their winding.
The SVG defines the even–odd rule by saying:
The rule can be seen in effect in many vector graphic programs (such as Freehand or Illustrator), where a crossing of an outline with itself causes shapes to fill in strange ways.
On a simple curve, the even–odd rule reduces to a decision algorithm for the point in polygon problem.
The SVG computer vector graphics standard may be configured to use the even–odd rule when drawing polygons, though it uses the Nonzero-rule by default.[1], w3c.org, retrieved 2019-03-28
"""Determine if the point is on the path, corner, or boundary of the polygon
Args:
x -- The x coordinates of point.
y -- The y coordinates of point.
poly -- a list of tuples [(x, y), (x, y), ...]
Returns:
True if the point is in the path or is a corner or on the boundary"""
c = False
for i in range(len(poly)):
ax, ay = poly[i]
bx, by = poly[i - 1]
if (x == ax) and (y == ay):
# point is a corner
return True
if (ay > y) != (by > y):
slope = (x - ax) * (by - ay) - (bx - ax) * (y - ay)
if slope == 0:
# point is on boundary
return True
if (slope < 0) != (by < ay):
c = not c
return c
|
|
